In many Geographic Information System (GIS) applications, as well as in the context of ample location-based services, such as online map services, navigational tools, dating applications, or the like, a search for the nearest object of interest with respect to a given location may be a common task. For example, a user may query which restaurant, hotel, hospital, gas station, another user, or the like, is the closest to her whereabouts.
One possible solution is to compute the distance to each object and select the nearest one, i.e. the object of the shortest distance thereto. However, such solution, though simple, is highly inefficient for practical situations, as its time complexity is linear in the input size.
In case the objects in question are points, a better solution is to employ a Voronoi diagram algorithm. A Voronoi diagram is a subdivision of a given space into cells, such that the points in each zone are the nearest to a specific input point. Thus, to find out the nearest object (i.e., input point) to a query point, it suffices to locate the cell in which the query point lies. This task may be accomplished in logarithmic time, by utilizing a point-location data structure constructed based on the Voronoi cells.
However, for objects of different kinds other than points, there are no efficient solutions that are commonly available and relatively easy to implement.